package com.example.lcpractice.lc;

import java.util.ArrayList;
import java.util.List;

/**
 * 42 2维接雨水
 *
 * <p>
 * Related Topics 数组 回溯 👍 2126 👎 0
 */
public class Lc42 {
    public static void main(String[] args) {
//        ListNode list = ListNode.getSingleLinkedList();
//        ListNode list2 = ListNode.getSingleLinkedList2();
//        System.out.println(mergeTwoLists(list2, list2));
        System.out.println();
    }

    /**
     * 时间复杂度：O(n²），遍历每一列需要 n，找出左边最高和右边最高的墙加起来刚好又是一个 n，所以是 n²。
     * <p>
     * 空间复杂度：O(1）
     *
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        int sum = 0;
        //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
        for (int i = 1; i <= height.length - 2; i++) {
            int max_left = 0;
            //找出左边最高
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }
            int max_right = 0;
            //找出右边最高
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > max_right) {
                    max_right = height[j];
                }
            }
            //找出两端较小的
            int lowerSide = Math.min(max_left, max_right);
            //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if (lowerSide > height[i]) {
                sum = sum + (lowerSide - height[i]);
            }
        }
        return sum;
    }

    /**
     * 动态规划
     *
     * @param height
     * @return
     */
    public static int trap2(int[] height) {
        int sum = 0;
        // max_left[i]代表对i列来说左最高 max_right代表对i列来说右边最高
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        //显然0没有左最高，且最右不符合条件
        for (int i = 1; i < height.length - 1; i++) {
            // 对i列  max_left[i - 1]是前一列取最高  height[i - 1]就是本列
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        //同上
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            // 对每列取出左最高,右最高的 比较 矮值
            int min = Math.min(max_left[i], max_right[i]);
            //较矮值大于当前值，则取雨水
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }
}
